\input{euler.tex}

\begin{document}

\problem[155]{Counting Resistor Circuits}

An electric circuit uses exclusively identical resistors of the same resistance $R$. The resistors can be connected in series or in parallel to form sub-units, which can then be connected in series or in parallel with other resistors or other sub-units to form larger sub-units, and so on up to a final circuit.

Using this simple procedure and up to $n$ identical resistors, we can make circuits having a range of different total resistances. For example, using up to $n=3$ resistors of $60\Omega$ each, we can obtain 7 distinct total resistance values: $180\Omega$, $120\Omega$, $90\Omega$, $60\Omega$, $40\Omega$, $30\Omega$, $20\Omega$. 

If we denote by $D(n)$ the number of distinct total resistance values we can obtain when using up to $n$ equal-valued resistors and the simple procedure described above, we have: $D(1)=1$, $D(2)=3$, $D(3)=7$, etc.

Find $D(18)$.

\solution

Given two circuits of resistance $a$ and $b$, let 
\begin{equation}
V_S(a, b) = a+b
\end{equation}
be the total resistance by connecting them in series, and 
\begin{equation}
V_P(a,b) = (a^{-1}+b^{-1})^{-1} = ab/(a+b)
\end{equation}
be the total resistance by connecting them in parallel. Let $A_n$ denote the set of all possible resistance values constructed from $n$ resistors of unit resistance by series and parallel connection. It is easy to see that $A_1 = \{1\}$ and
\begin{equation}
A_n = \left\{ V_S(a, b), V_P(a, b) \,|\, a \in A_k, b \in A_{n-k}, 1 \le k < n \right\} . \label{eq:115.5}
\end{equation}
Once we have iterated the elements in each $A_n$, we can find the total number of distinct resistance values as
\begin{equation}
D(n) = \# \{ A_1 \cup \cdots \cup A_n \} . \label{eq:115.6}
\end{equation}

While the above formula does give the correct answer, a straightforward implementation of it runs very slow when $n$ gets large. Hence, properties of equal-valued resistor network need to be studied. Without loss of generality, we assume the resistors to have unit resistance. The results can be scaled to hold for equal-valued resistors of non-unit resistance.

First, note that if a resistance value, $c$ can be constructed from $n$ unit resistors, then its reciprocal, $c^{-1}$, can also be constructed from these resistors. In fact, it is achieved by \emph{complementing} the circuit, i.e. changing parallel connections into series connections and vice versa. To see this, let $c'$ denote the complement of circuit $c$. If $c$ is a single unit resistor, then $c'=c=c^{-1}=1$, and the statement is true. If $c$ is a composite circuit, on the highest level it must be either a parallel connection or a series connection of two sub-circuits $a$ and $b$, each with fewer number of resistors. Suppose the statement is true for circuits with fewer number of resistors, and note that complementing a series connection gives
\[
V'_S(a,b) = V_P(a', b') = V_P(a^{-1}, b^{-1}) = (a+b)^{-1} = V_S(a,b)^{-1} ,
\]
and complementing a parallel connection of $a$ and $b$ gives
\[
V'_P(a,b) = V_S(a', b') = V_S(a^{-1}, b^{-1}) = a^{-1} + b^{-1} = V_P(a,b)^{-1} .
\]
Hence $c' = c^{-1}$ is also true, and this concludes the proof. Note that this property only holds for circuits constructed from equal-valued resistors.

With this result in hand, we only need to store resistance values greater than or equal to one, and their reciprocals will be implicitly included. Let $B_n$ denote the subset of $A_n$ with values greater than or equal to one. Thus we have
\begin{align}
B_n = \Big\{ (a+b), (a+b^{-1}), (a^{-1}+b), \max \left( a^{-1}+b^{-1},(a^{-1}+b^{-1})^{-1} \right) \notag \\
\,\big|\, a \in B_k, b \in B_{n-k}, 1 \le k < n \Big\} . \label{eq:155.b1}
\end{align}
And it follows that
\begin{equation}
D(n) = \# \{ B_1 \cup \cdots \cup B_n \} \times 2 - 1 . \label{eq:155.b2}
\end{equation}
This approach, compared to the original ones \eqref{eq:115.5} and \eqref{eq:115.6}, saves half the memory and reduces some overhead in looping.

Another important observation can be made by listing the first few $B_n$ in reduced fractional values,
\begin{align}
B_1 &= \left\{ \frac11 \right\} , \notag \\
B_2 &= \left\{ \frac21 \right\}, \notag \\
B_3 &= \left\{ \frac31, \frac32 \right\}, \notag \\
B_4 &= \left\{ \frac11, \frac41, \frac52, \frac43, \frac53 \right\} \notag \\
B_5 &= \left\{ \frac21, \frac51, \frac72, \frac73, \frac83, \frac54, \frac74, \frac65, \frac75, \frac85, \frac76 \right\} . \notag
\end{align}
We claim (without proof) that the largest numerator of the fractional values in $B_n$ is equal to $F_{n+1}$, where $F_k$ is the Fibonacci sequence $\{ 1, 1, 2, 3, 5, 8, \ldots \}$. This observation limits the storage that we need to reserve for the exact fractional values, which is critical for an efficient implementation. For example, for 18 resistors, $F_{19}=4181$, so for each fraction we only need two bytes to store its denominator and two bytes to store its numerator. 

This observation is also useful in deriving an upper bound for the size of $B_n$. Since $B_n$ only contains fractions with numerators not exceeding $F_{n+1}$, it is a subset (after exchanging numerator and denominator) of the Farey sequence of order $F_{n+1}$, which contains \emph{all} fractions with denominators not exceeding $F_{n+1}$. The asymptotic size of the Farey sequence of order $n$ is $3 n^2 / \pi^2$, and the Fibonacci number $F_n$ is close to $1.618^n / \sqrt{5}$. So the number of elements in $B(n)$ is asymptotically bounded by $0.16 \times 2.62^n$. For $n=18$, this is about $5.4 \times 10^6$. Obviously, the bound also holds for $D(n)$. 

One more optimization can be introduced by noting that in equation \eqref{eq:155.b1}, certain combinations are redundant. For example, suppose we already know $B_1$ through $B_5$, and want to find $B_6$. According to \eqref{eq:155.b1}, we need to iterate all pairs in the outer products $B_1 \otimes B_5$, $B_2 \otimes B_4$, and $B_3 \otimes B_3$. However, notice that the pair $\{1/1, 2/1\}$ is in both $B_1 \otimes B_5$ and $B_4 \otimes B_2$. Therefore one of the iterations is redundant.

Such redundancy can be reduced by operating on the \emph{differences} of $B_n$s. Specifically, define $C_0 = \{ \phi \}$ and
\[
C_n = B_n \setminus \left( B_1 \cup \cdots \cup B_{n-1} \right) .
\]
That is, $C_n$ consists of the \emph{additional} resistance values by using $n$ resistors instead of using $n-1$ or fewer resistors. 
% Similarly, define $E_0 = \{ \phi \}$ and
% \[
% E_n = \left( B_1 \cup \cdots \cup B_{n-1} \right) \setminus B_n ,
% \]
% which can be interpreted as the \emph{missing} resistance values as a result of using exactly $n$ resistors instead of using $n-1$ or fewer resistors.
It is easy to see that any \emph{additional} resistance value constructed from $n$ resistors must come from connecting two sub-circuits both of which has a resistance value that is not present in any circuits with fewer resistors. Hence, we can rewrite equation \eqref{eq:155.b1} as
\begin{align}
C_n = \Big\{ (a+b), (a+b^{-1}), (a^{-1}+b), \max \left( a^{-1}+b^{-1},(a^{-1}+b^{-1})^{-1} \right) \notag \\
\,\big|\, a \in C_k, b \in C_{n-k}, 1 \le k < n \Big\} \setminus \left(C_1 \cup \cdots \cup C_{n-1} \right)  . \label{eq:155.c1}
\end{align}
And it follows that
\begin{equation}
D(n) = \# \{ C_1 \cup \cdots \cup C_n \} \times 2 - 1 . \label{eq:155.c2}
\end{equation}

Note that equations \eqref{eq:155.c1} and \eqref{eq:155.c2} can only be used to find the number of resistance values constructible from $n$ \emph{or fewer} resistors; it is not able to find the number of resistance values from \emph{exactly} $n$ resistors. If that number is required, the less efficient equations \eqref{eq:155.b1} and \eqref{eq:155.b2} can be used.

Finally, an implementation trick for optimization is to keep track of the running union of $C_1 \cup \cdots \cup C_n$. It turns out that this set of running union is \emph{dense} in the sense that a large proportion of reduced fractional values, among all possible fractional values bounded by the numerator size, are present. Therefore it is efficient to store the union as a bitset, hence achieving constant complexity element addition and finding while using the memory efficiently.

With the above optimizations, the algorithm finds $D(18)$ in under one second, and finds $D(22)$ in 52 seconds.

\complexity

The majority of work is done in constructing $C_n$ using equation \eqref{eq:155.c1}. The number of elements in $C_k$ is of order $\BigO(2.62^k)$, and the number of elements in $C_{n-k}$ is of order $\BigO(2.62^{n-k})$. So given $k$, the complexity of computing the outer product is $\BigO(2.62^n)$. Since there are $\lfloor n / 2 \rfloor$ possible choices of $k$, constructing each $C_n$ takes $\BigO(n \times 2.62^n)$. There are $N = 18$ such sets to construct, so the total time is roughly $\BigO(N \times 2.62^N)$.

Memory usage include storing each $C_n$ for $n = 1$ to $N$, which costs $\BigO(2.62^N)$, and storing the running union of $C_n$ in a bitset, which also costs $\BigO(2.62^N)$.

Time complexity: $\BigO(N \times 2.62^N)$.

Space complexity: $\BigO(2.62^N)$.

\answer

3857447

\reference

http://mathworld.wolfram.com/ResistorNetwork.html

http://arxiv.org/abs/1004.3346/

http://oeis.org/A153588

http://en.wikipedia.org/wiki/Farey\_sequence

\end{document} 
